package a09_贪心算法;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <p>
 * a19_划分字母区间
 * </p>
 *
 * @author flyduck
 * @since 2025/1/16
 */
public class a19_划分字母区间 {
    public static void main(String[] args) {
        a19_划分字母区间 test = new a19_划分字母区间();
        List<Integer> list = test.partitionLabels("ababcbacadefegdehijhklij");
        System.out.println(list);
    }
    public List<Integer> partitionLabels(String s) {
        char[] chars = s.toCharArray();
        //求每个元素最远位置
        Map<Character,Integer> map = new HashMap<>();
        for (int i = 0; i < chars.length; i++) {
            map.put(chars[i],i);
        }

        //分割
        List<Integer> resultList = new ArrayList<>();
        int startIdx = 0;
        int endIdx = 0;
        int maxIdx = Integer.MIN_VALUE;
        while (endIdx < chars.length){
            //计算最远处
            maxIdx = Math.max(map.get(chars[endIdx]), maxIdx);
            if(endIdx == maxIdx){//切割
                resultList.add(endIdx - startIdx + 1);
                endIdx++;
                startIdx = endIdx;
            }else {
                endIdx++;
            }
        }
        return resultList;

    }
}
